package leetcode.lcp.lcp20230422;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

import leetcode.helper.H;

//Solution3Test
public class Solution3 {

	public int fieldOfGreatestBlessing(int[][] forceField) {
		int len = forceField.length;
		TreeSet<Double> set = new TreeSet<>();
		for (int i = 0; i < len; i++) {
			int[] f = forceField[i];
			double x = f[0], y = f[1], z = f[2];
			double h = (double) z / 2;
			double u = y + h, d = y - h, l = x - h, r = x + h;
			set.add(u);
			set.add(d);
			set.add(l);
			set.add(r);
		}
		int idx = 0;
		Map<Double, Integer> map = new HashMap<>();
		for (double d : set) {
			map.put(d, idx++);
		}
		int[][] arr = new int[len * 2][4];
		for (int i = 0, j = -1; i < len; i++) {
			int[] f = forceField[i];
			double x = f[0], y = f[1], z = f[2];
			double h = (double) z / 2;
			int u = map.get(y + h), d = map.get(y - h), l = map.get(x - h), r = map.get(x + h);
			arr[++j] = new int[] { d, l, r, 1 };
			arr[++j] = new int[] { u, l, r, -1 };
		}
		Node root = new Node(0, idx);
		Arrays.sort(arr, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[3] - a[3]);
		int ans = 0;
		for (int i = 0; i < len * 2; i++) {
			int[] c = arr[i];
			int a = c[0], l = c[1], r = c[2], f = c[3];
			root.add(l, r, f);
			ans = Math.max(ans, root.max);
		}
		return ans;
	}

	class Node {

		private int LeftRange, Mid, RightRange;
		private Node leftChild, rightChild;
		private int value;
		public int max = 0;

		public Node(int left, int right) {
			this.LeftRange = left;
			this.RightRange = right;
			this.Mid = ((this.RightRange - this.LeftRange) >> 1) + this.LeftRange;
			this.value = 0;
			this.max = 0;
		}

		private Node leftNode() {
			if (this.leftChild == null) {
				this.leftChild = new Node(this.LeftRange, this.Mid);
			}
			return this.leftChild;
		}

		private Node rightNode() {
			if (this.rightChild == null) {
				this.rightChild = new Node(this.Mid + 1, this.RightRange);
			}
			return this.rightChild;
		}

		private void addValue(int value) {
			this.value += value;
			this.max += value;
		}

		public void add(int left, int right, int add) {
			if (left > right) {
				return;
			}
			if (left == this.LeftRange && right == this.RightRange) {
				this.addValue(add);
			} else {
				pushdown();
				this.leftNode().add(left, Math.min(this.Mid, right), add);
				this.rightNode().add(Math.max(this.Mid + 1, left), right, add);
				this.max = Math.max(this.leftNode().max, this.rightNode().max);
			}
		}

		private void pushdown() {
			this.leftNode().addValue(this.value);
			this.rightNode().addValue(this.value);
			this.value = 0;
		}

	}

}
